from random import randint
import sys
from os import times
from time import time

class Node(object):
    def __init__(self,name):
        self.Name = name
        self.Visited = False
        self.NNeighbours = 0
        self.LinkWeight = []
        self.NeighbourIndex = []
        
    def Set_Visited(self):
        self.Visited = True
        
    def Unvisited(self):
        self.Visited = False
        
    def __str__(self):
        s = ''
        s += 'Name: ' + str(self.Name) + "\n"
        s += 'Visited: ' + str(self.Visited) + "\n"
        s += 'Number of Neighbours: ' + str(self.NNeighbours) + "\n"
        s += 'LinkWeight: ' + str(self.LinkWeight) + "\n"
        s += 'Neighbour Index: ' + str(self.NeighbourIndex)
        return s
        
    def __eq__(self, other):
        return self.Visited == other

    def __ne__(self, other):
        return not self.__eq__(other)

class Graph(object):
    def __init__(self, N, minL, maxL, minP, maxP):
        self.N = N
        self.minL = minL
        self.maxL = maxL
        self.minP = minP
        self.maxP = maxP
        self.Graph = []
        self.numL = None
        self.tpL = None
        self.NodeList = []
        self.DijkstraDist = None
        self.DijkstraPrev = None
        self.DijkstraCost = 0
        
        self.FWDist = None 
        self.FWPath = None
        self.Result = None
        self.DFSPath = [0 for i in xrange(self.N*100)]
        self.S_DFSPath = [0 for i in xrange(self.N*100)]
        self.DFSPath_G = [0 for i in xrange(self.N*100)]
        self.S_DFSPath_G = [0 for i in xrange(self.N*100)]
        self.BFSPath = [0 for i in xrange(self.N)]
        self.S_BFSPath = [0 for i in xrange(self.N)]
        self.GloutonVisited = []
        self.GloutonNVisited = 0
        
    def GetResult(self):
        return str(self.Result)
        
    def GenerateNodeList(self):
    
        for i in range(0,self.N):
            self.NodeList.append(Node(str(i)))    
            for j in range(0,self.N):
                if self.Graph[i][j] > 0:
                    self.NodeList[i].NNeighbours += 1
                    self.NodeList[i].NeighbourIndex.append(j)
                    self.NodeList[i].LinkWeight.append(self.Graph[i][j])
   
   
   
    def Dijkstra(self, src, dst=None):
        Visited = [False for i in xrange(self.N)]
        Dist = [float('inf') for i in xrange(self.N)]
        Previous = [None for i in xrange(self.N)]
        
        Visited[src] = True
        nVisited = 1
        
        for i in range(0,len(self.NodeList[src].NeighbourIndex)):
            Dist[self.NodeList[src].NeighbourIndex[i]]  = self.NodeList[src].LinkWeight[i]
        
        while nVisited < self.N:
            ''' Find plus petit non visiter avec le plus petit D'''
            check = float('inf')
            closest = -1
            for i in range(0,len(Dist)):
                if Dist[i] < check and Visited[i] == False:
                    check = Dist[i]
                    closest = i
                    
            
            Visited[closest] = True
            nVisited += 1
            
            for v in range(0, len(self.NodeList[closest].NeighbourIndex)):
                if Dist[self.NodeList[closest].NeighbourIndex[v]] > Dist[closest] + self.NodeList[closest].LinkWeight[v]:
                    Dist[self.NodeList[closest].NeighbourIndex[v]] = Dist[closest] + self.NodeList[closest].LinkWeight[v]
                    Previous[self.NodeList[closest].NeighbourIndex[v]] = closest
            
            #print 'Dist: ' + str(Dist)
            #print 'Visited: ' + str(Visited)
            #print 'Prev: ' + str(Previous)
            
        self.DijkstraDist = Dist
        self.DijkstraPrev = Previous
        
        self.DijkstraVisited = []
        for i in range(0,len(Visited)):
            if Visited[i] == True:
                self.DijkstraVisited.append(i)
        
        
        self.DijkstraNVisited = nVisited 
        
        
        if dst != None:
            self.Result = self.DijkstraPath(src, dst)
        
    def DijkstraPath(self,src, dst):
        if self.DijkstraDist == None or self.DijkstraPrev == None or self.DijkstraDist == [] or self.DijkstraPrev == []:
            return []
        if src == dst:
            return [src]
            self.DijkstraCost = 0
        if self.DijkstraDist[dst] == -1:
            return []
        
        
        nextHop = dst
        path = [dst]
        
        while self.DijkstraPrev[nextHop] != None:
            path.append(self.DijkstraPrev[nextHop])
            nextHop = self.DijkstraPrev[nextHop]
        
        path.append(src)
        
        s = src
        path = path[::-1]
        for d in path:
            self.DijkstraCost += self.Graph[s][d]
            s = d 
        
        return path
        
    
    def FloydWarshall(self,src,dst=None):
        path = [[None for j in xrange(self.N)] for i in xrange(self.N)]
        dist = [[float('inf') for j in xrange(self.N)] for i in xrange(self.N)]
        
        for i in range(0, self.N):
            for j in range(0, self.N):
                if self.Graph[i][j] >= 0:                    
                    dist[i][j] = self.Graph[i][j]
                else:
                    dist[i][j] = float('inf')
                path[i][j] = -1
            
        for k in range(0, self.N):
            for i in range(0, self.N):
                for j in range(0, self.N):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        path[i][j] = k
        
        self.FWPath = path
        self.FWDist = dist
        self.FWNVisited = self.N
        self.FWVisited = [i for i in range(0,self.N)]
        
        if dst != None:
            self.Result = self.FloydWarshallPath(src,dst)
        
   
    def FloydWarshallPath(self,src,dst):
        if self.FWDist == None or self.FWPath == None:
            return []
        if src == dst:
            return [src]
        if self.FWDist[src][dst] < 0:
            return []
        
        path = [dst]
        nextNode = dst
        while self.FWPath[src][nextNode] != -1:
            path.append(self.FWPath[src][nextNode])
            nextNode = self.FWPath[src][nextNode]
            
        path.append(src)
        
        path = path[::-1]
        s = src
        self.FWCost = 0
        for d in path:
            self.FWCost += self.Graph[s][d]
            s = d 
        return path


    def DFS(self,Node_List,Source,Destination,p=0):
        if Node_List[Source].Visited:
            return False
        Node_List[Source].Set_Visited()
        self.GloutonVisited.append(Source)
        self.GloutonNVisited += 1

        find = False
        k = 0    
        v = 0 
        while k < Node_List[Source].NNeighbours and find == False:
            v = Node_List[Source].NeighbourIndex[k]
            if (Node_List[v].Name) == str(Destination):
                find = True
                #path[p+1] = Node_Lkist[v].Name
                try:
                    self.DFSPath[p+1] = Node_List[v].Name
                except:
                    pass
            else:
                find = self.DFS(Node_List,v,Destination,p+1)
            if find == False:
                k = k+1
        if find == True:
            Node_List[Source].Set_Visited()
            #self.GloutonNVisited += 1
            #path[p] = Node_List[source].Name
            self.DFSPath[p] = Node_List[Source].Name
            return True 
        else:
            return False   
            

    def DFS_G(self,Node_List,Source,Destination,p=0):
        if Node_List[Source].Visited:
            return False
        Node_List[Source].Set_Visited()
        self.GloutonVisited.append(Source)
        self.GloutonNVisited += 1
        
        find = False
        k = 0    
        v = 0 
        tab = []
        
        while k < Node_List[Source].NNeighbours and find == False:
            for i in range(0,Node_List[Source].NNeighbours):
                tab.append((Node_List[Source].NeighbourIndex[i],Node_List[Source].LinkWeight[i]))
                tab.sort(key=lambda tup: tup[1])
            #print "NB NH : " + str(Node_List[Source].NNeighbours)
            #print "len : " + str(len(Node_List[Source].NeighbourIndex))
            v = tab[k][0]
            #print "v is : " + str(v)
            if Node_List[v].Name == str(Destination):
                find = True
                self.DFSPath_G[p+1] = Node_List[v].Name
            else:
                find = self.DFS_G(Node_List,v,Destination,p+1)
            if find == False:
                k = k+1
        if find == True:
            Node_List[Source].Set_Visited()
            #path[p] = Node_List[source].Name
            self.DFSPath_G[p] = Node_List[Source].Name
            return True    
        else:
            return False
    
    def BFS(self,Node_List,Source,Destination):
        if Destination > (len(Node_List)-1):
            print "!!! Destination is not in Node List !!!"
            return False
            
        if Node_List[Source].Visited:
            print "!!! Node have already be visited !!!"
            return False
            
        Node_List[Source].Set_Visited()
        self.GloutonVisited.append(Source)
        self.GloutonNVisited += 1
        

        
        find = False
        k = 0    
        v = 0 
        a = Source
        queue = []
        queue.append(a)
        path = []
        s_path = []
        
        while len(queue) > 0 and find == False:
            a = queue.pop(0)
            path.append(str(a))
            k = 0
            #print "a : [" + str(a) + "]"
            while k < Node_List[a].NNeighbours and find == False:
                #print "k : ->->->" + str(k)
                v = Node_List[a].NeighbourIndex[k]
                #print "v : ->" + str(v)
                #if Node_List[v].Visited:
                if Node_List[v].Name == str(Destination):
                    find = True
                    path.append(Node_List[v].Name)
                else:
                    if v not in queue:
                        queue.append(v)    
                    k = k+1
                     
        if find == True:
            Node_List[Source].Set_Visited()
            self.GloutonNVisited += 1
            self.GloutonVisited.append(Source)
            #path[p] = Node_List[source].Name
            #print "Find path...There it is : " + str(path)
            self.BFSPath = path
            #s_path = self.Backtrace_FS(Node_List,path)
            #print "Shortes path is : " + str(s_path)
            return True
        else:
            print "No path was found"
            return False    
    
    def Backtrace_FS(self,Node_List,path):
        s_path = []
        l = (len(path)-1)
        #s_path.append(path[l])
        find = False
        
        while l > 0:
            for i in range (0,l):
                if(int(path[l]) in Node_List[int(path[i])].NeighbourIndex):
                    s_path.append(path[l])
                    if l is not path[0]:
                        l = i
                    find = True
                    break
                else:
                    find = False

            if find:
                pass
            else:
                l = l - 1
        s_path.append(path[0])
        s_path.reverse()
        self.GloutonCost = 0
        s = s_path[0]
        
        for d in s_path:
            if self.Graph[int(s)][int(d)] > 0:
                self.GloutonCost += self.Graph[int(s)][int(d)]
              
        return s_path

    def Reset_Graph(self):
        l = len(self.NodeList)
        for x in range(0,l):
            self.NodeList[x].Visited = False

    def Normalize(self):
        
        for i in range(0, len(self.S_BFSPath )):
            if self.S_BFSPath[i] == 0:
                self.S_BFSPath = self.S_BFSPath[:i]
                break

        for i in range(0, len(self.DFSPath )):
            if self.DFSPath[i] == 0:
                self.DFSPath = self.DFSPath[:i]
                break
        
        for i in range(0, len(self.S_DFSPath)):
            if self.S_DFSPath[i] == 0:
                self.S_DFSPath = self.S_DFSPath[:i]
                break
        
        for i in range(0, len(self.DFSPath_G)):
            if self.DFSPath_G[i] == 0:
                self.DFSPath_G = self.DFSPath_G[:i]
                break
        
        for i in range(0, len(self.S_DFSPath_G)):
            if self.S_DFSPath_G[i] == 0:
                self.S_DFSPath_G = self.S_DFSPath_G[:i]
                break
        
        for i in range(0, len(self.BFSPath )):
            if self.BFSPath[i] == 0:
                self.BFSPath = self.BFSPath[:i]
                break
        
        
        
        
        
        

    def Read(self, fname):
        try:
            f = open(fname, 'r')
        except:
            raise
            return
        
        self.N = int(f.readline().strip()) 
        d = f.readlines()
        for i in d:
            i = i.strip().split(" ")
            i = filter(lambda a: a != '', i)
            for n in range(0, len(i)):
                i[n] = int(i[n])
            self.Graph.append(i)
            
        f.close()
        
    def Generate(self):
        self.Graph = [[-1 for j in xrange(self.N)] for i in xrange(self.N)]
        self.numL = [0 for i in xrange(self.N)]
        self.tpL = [0 for i in xrange(self.N)]
        self.DFSPath = [0 for i in xrange(self.N*100)]
        self.S_DFSPath = [0 for i in xrange(self.N*100)]
        self.DFSPath_G = [0 for i in xrange(self.N*100)]
        self.S_DFSPath_G = [0 for i in xrange(self.N*100)]
        self.BFSPath = [0 for i in xrange(self.N*100)]
        self.S_BFSPath = [0 for i in xrange(self.N*100)]
        
        
        for n in range(0,self.N):
            self.Graph[n][n] = 0
            try:
                self.numL[n] = int(self.minL + randint(0,99999)) % (self.maxL - self.minL)
            except ZeroDivisionError:
                self.numL[n] = self.minL
            
        for k in range(1,self.minL):
            for n in range(0, self.N):
                if self.numL[n] > 0:
                    k = 0
                    for p in range(0, self.N):
                        if self.Graph[n][p] < 0 and self.numL[p] > 0:
                            self.tpL[k] = p
                            k += 1
                    if k>0:
                        a = self.tpL[int(randint(0, 99999) % k)]
                        try:
                            p = int(self.minL + randint(0,99999)) % (self.maxP - self.minP)
                        except ZeroDivisionError:
                            p = self.minP
                        self.Graph[n][a] = p                        
                        self.Graph[a][n] = p
                        self.numL[n] -= 1
                        self.numL[a] -= 1

    def __len__(self):
        return self.N
        
    def __str__(self):
        s = ''
            
        for i in self.Graph:
            s += str(i)
            s += "\n"
        return s
    
    
if __name__ == "__main__":

    TestMode = False
    TestAlgo = 'DFS'
    #TestAlgo = None
    if TestMode:
        G = Graph(8,3,15,1,1)
        G.Generate()
        G.Graph = [
        [0,3,4,2,-1,-1,6,-1,-1,-1],
        [3,0,-1,1,-1,-1,-1,5,-1,-1],
        [4,-1,0,-1,1,7,3,-1,-1,-1],
        [2,1,-1,0,5,-1,-1,6,4,-1],
        [-1,-1,1,5,0,10,-1,-1,3,-1],
        [-1,-1,7,-1,10,0,7,-1,-1,-1],
        [6,-1,3,-1,-1,7,0,-1,-1,-1],
        [-1,5,-1,6,-1,-1,-1,0,-1,2],
        [-1,-1,-1,4,3,-1,-1,-1,0,9],
        [-1,-1,-1,-1,-1,-1,-1,2,9,0]]
        
        G.GenerateNodeList()
        NL = G.NodeList
        
        if TestAlgo == 'Marshal':
            x = G.FloydWarshall(0,5)
            print 'path: ' + str(x)       
        elif TestAlgo == 'BFS':
            print 'BFS'
            print G
            G.BFS(NL,0,7)
            G.S_BFSPath = G.Backtrace_FS(NL,G.BFSPath)
            print G.BFSPath
            print G.S_BFSPath
        elif TestAlgo == 'DFS':
            print 'DFS1'
            print G
            G.DFS2(NL,0,7)
            G.S_DFSPath = G.Backtrace_FS(NL,G.DFSPath)
            G.Normalize()
            print G.DFSPath
            print G.S_DFSPath
        elif TestAlgo == 'DFS_G':
            print 'DFS_G'
            print G
            G.DFS_G(G.NodeList,0,7)
            G.S_DFSPath_G = G.Backtrace_FS(NL,G.DFSPath_G)
            print G.DFSPath_G
            print G.S_DFSPath_G
        else:
            G.Dijkstra(0,5)
        
    else:
        choice = int(raw_input("1. Labyrinthe\n2. Toure de Londre\n3. Carte Routiere\n> "))
        data = int(raw_input("1. Lectures d'un ficiher\n2. Graphe generer aleatoirement\n3.Graphe de l'enonce\n4. Mini-Graphe\n> "))
        
        if data == 1:
            fname = raw_input("Nom du ficher\n> ")
            G = Graph(10,3,15,4,9)
            try:
                G.Read(fname)
            except:
                print 'Impossible d\'ouvrir le fichier...\n'
                sys.exit(-1)
        elif data == 2:
            N = int(raw_input("N: "))
            minL = int(raw_input("minL: "))
            maxL = int(raw_input("maxL: "))
            minP = int(raw_input("minP: "))
            maxP = int(raw_input("maxP: "))
            G = Graph(N, minL, maxL, minP, maxP)
            G.Generate()
        elif data == 3:
            G = Graph(10,3,15,4,9)
            G.Graph = [
                [0,3,4,2,-1,-1,6,-1,-1,-1],
                [3,0,-1,1,-1,-1,-1,5,-1,-1],
                [4,-1,0,-1,1,7,3,-1,-1,-1],
                [2,1,-1,0,5,-1,-1,6,4,-1],
                [-1,-1,1,5,0,10,-1,-1,3,-1],
                [-1,-1,7,-1,10,0,7,-1,-1,-1],
                [6,-1,3,-1,-1,7,0,-1,-1,-1],
                [-1,5,-1,6,-1,-1,-1,0,-1,2],
                [-1,-1,-1,4,3,-1,-1,-1,0,9],
                [-1,-1,-1,-1,-1,-1,-1,2,9,0]]
        elif data == 4:
            G = Graph(10,3,15,4,9)
            G.Graph = [
            [0,1,-1,1,-1,-1,-1,-1,-1,-1,-1],
            [1,0,1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,1,0,-1,1,-1,-1,-1,-1,-1,-1],
            [1,-1,-1,0,-1,-1,1,-1,-1,-1,-1],
            [-1,-1,1,-1,0,1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,1,0,-1,-1,-1,-1,-1],
            [-1,-1,-1,1,-1,-1,0,1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,1,0,1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,1,0,1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,1,0,1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,1,0]
            ]
            
            
        else:
            print 'Choix invalide\n'
            sys.exit(-1)
            
        G.GenerateNodeList()
        NL = G.NodeList

        
        if choice == 1 or choice == 2: # Labyrinthe or Toure de Londre
            algo = int(raw_input("1. DFS\n2. BFS\n> "))
            src = int(raw_input("Source: "))
            dst = int(raw_input("Destination: "))
            n1 = time()
            if algo == 1:
                #print G.DFSPath
                G.DFS(NL,src,dst)
                G.S_DFSPath = G.Backtrace_FS(NL,G.DFSPath)
                G.Normalize()
                print 'Cout: ' + str(G.GloutonCost)
                print 'Liste des noeuds visiter: ' + str(G.DFSPath)
                print 'Nombre Visiter: '  + str(len(G.DFSPath))
                if choice != 1:
                    print 'Chemin: ' + str(G.S_DFSPath)
            elif algo == 2:
                #print G.BFSPath
                G.BFS(NL,src,dst)
                G.S_BFSPath = G.Backtrace_FS(NL,G.BFSPath)
                G.Normalize()
                print 'Cout: ' + str(G.GloutonCost)
                print 'Liste des noeuds visiter: ' + str(G.BFSPath)
                print 'Nombre Visiter: '  + str(len(G.BFSPath))
                if choice != 1:
                    print 'Chemin: ' + str(G.S_BFSPath)
            else:
                print 'Choix Invalide'
                sys.exit(-1)

        elif choice == 3:
            algo = int(raw_input("1. Dijkstra\n2. Floyd-Warshall\n3.Glouton\n> "))
            src = int(raw_input("Source: "))
            dst = int(raw_input("Destination: "))
            n1 = time()
            if algo == 1:
                G.Dijkstra(src, dst)
                print 'Cout: ' + str(G.DijkstraCost)
                print 'Liste des noeuds visiter: ' + str(G.DijkstraVisited)
                print 'Nombre Visiter: '  + str(G.DijkstraNVisited)
                print 'Chemin: ' + str(G.Result)
            elif algo == 2:
                G.FloydWarshall(src, dst)
                print 'Cout: ' + str(G.FWCost)
                print 'Liste des noeuds visiter: ' + str(G.FWVisited)
                print 'Nombre Visiter: '  + str(G.FWNVisited)
                print 'Chemin: ' + str(G.Result)
            elif algo == 3:
                G.DFS_G(NL,src, dst)
                G.S_DFSPath_G = G.Backtrace_FS(NL,G.DFSPath_G)
                G.Normalize()
                print 'Cout: ' + str(G.GloutonCost)
                print 'Liste des noeuds visiter: ' + str(G.DFSPath_G)
                print 'Nombre Visiter: '  + str(G.GloutonNVisited)
                print 'Chemin: ' + str(G.S_DFSPath_G)
            else:
                print 'Choix Invalide'
                sys.exit(-1)

        else:
            print 'Choix invalide'
            sys.exit(-1)
        n2 = time()
        
        #print str((n2[4]-n1[4])) + ' ms'
        print str((n2-n1)*1000) + ' ms'
#        print n2
#        print n1
        #print G.GetResult()

